/*
 * Ken Anderson, 2009
 */

#ifndef HEURISTIC_H
#define HEURISTIC_H

#include "Graph.h"
#include "Search.h"
#include "hash_map.h"
#include <string>

// Declaration
class AStar;
typedef HashMap<const Node*, unsigned int> NodeValueMap_t;

// The Heuristic is used to provide an estimate of the remaining distance 
// from a current node to the goal node in a given graph.
// All heuristics must derive from this abstract class.
class Heuristic
{
protected:
	Graph * mGraph;
	Node  * mGoal;
	float mMaxValue;
	int mNumExpanded;	// Some heuristics require node expansions.
	std::string mName;

public:
	Heuristic();
	Heuristic( Graph * graph, const std::string name );
	virtual ~Heuristic();

	// Only recalculates the heuristic if absolutely necessary (ie the goal changes)
	// The start may be NULL.  The goal may not be NULL.
	// Override this function if alternative initialization is required.
	virtual void Init( Node * start, Node * goal );	

	// Getters
	std::string &GetName() { return mName; };
	virtual float GetValue( Node* ) = 0;
	virtual float ShowValue( Node * node ) = 0;
	Graph * GetGraph() { return mGraph; };
	float GetMaxValue() ;	// Caution: This is INEFFICIENT on the 1st call!
	int NumExpandedNodes() { return mNumExpanded; };
	virtual int GetNumAbstractNodes() = 0;
	virtual unsigned int GetMaxOpenListSize() {return 0; };	// Overload if applicable

	void print( FILE * stream );
};

// Abstract class
// Resumable heuristics calculate the heuristic values on-demand.
// If another heuristic value is requested that is not already calculated, 
// heuristic calculation will resume until the value is found.
class ResumableHeuristic : public Heuristic
{
protected:
	bool mOnDemand;
public:
	ResumableHeuristic() {};
	// name is the name of the heuristic
	// onDemand - if set to false, the heuristic values for the entire graph are calculated.
	ResumableHeuristic( Graph * graph, const std::string name, bool onDemand=true ) : Heuristic(graph,name),mOnDemand(onDemand) {};
};


//////////////////////////////////////////////////////////////////////////////
//////////////////// Derived Classes /////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////

// All heuristic values are zero.
class ZeroHeuristic : public Heuristic
{
public:
	ZeroHeuristic( Graph * graph );
	virtual float GetValue( Node* node ) { return 0.0; };
	virtual float ShowValue( Node * node ) {return GetValue(node);};
	virtual int GetNumAbstractNodes() {return 0;}
};

// The sum of the straight-line distances in the cardinal directions (x and y)
class ManhattanDistanceHeuristic : public Heuristic
{
public:
	ManhattanDistanceHeuristic( Graph * graph );
	virtual float GetValue( Node* node );
	virtual float ShowValue( Node * node ) {return GetValue(node);};
	virtual int GetNumAbstractNodes() {return 0;}
};

// Straight-line distance in the x direction
class XDistanceHeuristic : public Heuristic
{
public:
	XDistanceHeuristic( Graph * graph );
	virtual float GetValue( Node* node );
	virtual float ShowValue( Node * node ) {return GetValue(node);};
	virtual int GetNumAbstractNodes() {return 0;}
};

// Straight-line distance in the y direction
class YDistanceHeuristic : public Heuristic
{
public:
	YDistanceHeuristic( Graph * graph );
	virtual float GetValue( Node* node );
	virtual float ShowValue( Node * node ) {return GetValue(node);};
	virtual int GetNumAbstractNodes() {return 0;}
};

// The exact distance (calculated using BFS)
class ResumablePerfectHeuristic : public ResumableHeuristic
{
private:
	Heuristic * mBackwardsHeuristic;
	AStar * mBackwardsSearch;
public:
	ResumablePerfectHeuristic( Graph * graph, bool onDemand=true, bool useHeuristic=true );
	virtual ~ResumablePerfectHeuristic();
	void Init( Node * start, Node * goal );
	virtual float GetValue( Node * node );
	virtual float ShowValue( Node * node );
	virtual int GetNumAbstractNodes() {return mGraph->GetNumOfNodes();}
	virtual unsigned int GetMaxOpenListSize();
};

// The y distance in an abstract graph.
class ResumableYHeuristic : public ResumableHeuristic
{
private:
	Graph mAbstractGraph;	// Graph of abstract nodes and edges
  HashMap<const Node*,Node*> mSupernodes;
	Heuristic * mBackwardsHeuristic;
	AStar * mBackwardsSearch;

	void MarkNodeAndSuccessors( Node * subnode, int supernodeID, NodeValueMap_t & supernodeIDs );
	void InitAbstractGraph();
public:
	ResumableYHeuristic( Graph * graph, bool onDemand=true, bool useHeuristic=true );
	virtual ~ResumableYHeuristic();
	void Init( Node * start, Node * goal );
	virtual float GetValue( Node * node );
	virtual float ShowValue( Node * node );
	AStar* GetSearch() {return mBackwardsSearch;};
	virtual int GetNumAbstractNodes() {return mAbstractGraph.GetNumOfNodes();}
	virtual unsigned int GetMaxOpenListSize();
};

// The x distance in an abstract graph.
class ResumableXHeuristic : public ResumableHeuristic
{
private:
	Graph mAbstractGraph;	// Graph of abstract nodes and edges
  HashMap<const Node*,Node*> mSupernodes;
	Heuristic * mBackwardsHeuristic;
	AStar * mBackwardsSearch;

	void MarkNodeAndSuccessors( Node * subnode, int supernodeID, NodeValueMap_t & supernodeIDs );
	void InitAbstractGraph();
public:
	ResumableXHeuristic( Graph * graph, bool onDemand=true, bool useHeuristic=true );
	virtual ~ResumableXHeuristic();
	void Init( Node * start, Node * goal );
	virtual float GetValue( Node * node );
	virtual float ShowValue( Node * node );
	AStar* GetSearch() {return mBackwardsSearch;};
	virtual int GetNumAbstractNodes() {return mAbstractGraph.GetNumOfNodes();}
	virtual unsigned int GetMaxOpenListSize();
};

// The sum of the y & x distances in abstract graphs.
class ResumableAdditiveHeuristic : public Heuristic	
{
private:
	ResumableYHeuristic * mYHeuristic;
	ResumableXHeuristic * mXHeuristic;
public:
	ResumableAdditiveHeuristic( Graph * graph, bool onDemand=true, bool useHeuristic=true );
	virtual ~ResumableAdditiveHeuristic();
	void Init( Node * start, Node * goal );
	virtual float GetValue( Node * node );
	virtual float ShowValue( Node * node ) ;
	ResumableXHeuristic* GetXHeuristic() {return mXHeuristic;};
	ResumableYHeuristic* GetYHeuristic() {return mYHeuristic;};
	virtual int GetNumAbstractNodes() {return mYHeuristic->GetNumAbstractNodes()+mXHeuristic->GetNumAbstractNodes();}
	virtual unsigned int GetMaxOpenListSize();
};

#endif
